package experiment3;

import java.util.*;

public class GeneticAlgorithm {

    // 图的邻接矩阵 (权重)
    static int[][] graph = {
            {0, 2, 3, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
            {2, 0, 6, 7, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
            {3, 6, 0, 4, 2, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, 7, 4, 0, 4, 4, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, 2, 4, 0, 4, 3, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, 4, 0, 4, 3, Integer.MAX_VALUE, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 3, 4, 0, 3, 5, 4},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 3, 3, 0, 4, 4},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 5, 4, 0, 1},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 4, 4, 1, 0}
    };

    static int POPULATION_SIZE = 100;  // 种群大小
    static int NUM_GENERATIONS = 500;  // 迭代代数
    static double MUTATION_RATE = 0.1; // 变异率

    public static void main(String[] args) {
        GeneticAlgorithm ga = new GeneticAlgorithm();
        ga.run();
    }

    public void run() {
        List<int[]> population = initializePopulation(POPULATION_SIZE, graph.length);

        for (int generation = 0; generation < NUM_GENERATIONS; generation++) {
            // 计算适应度
            List<Integer> fitness = evaluateFitness(population);

            // 选择父代
            List<int[]> selectedPopulation = selection(population, fitness);

            // 交叉生成新一代
            List<int[]> offspring = crossover(selectedPopulation);

            // 变异
            mutate(offspring);

            // 更新种群
            population = new ArrayList<>(offspring);

            // 输出当前最优路径
            int bestIndex = fitness.indexOf(Collections.min(fitness));
            System.out.println("第 " + generation + " 代: 最优路径长度 = " + fitness.get(bestIndex));
        }
    }

    private List<int[]> initializePopulation(int populationSize, int numNodes) {
        List<int[]> population = new ArrayList<>();
        for (int i = 0; i < populationSize; i++) {
            int[] path = generateRandomPath(numNodes);
            population.add(path);
        }
        return population;
    }

    private int[] generateRandomPath(int numNodes) {
        int[] path = new int[numNodes];
        for (int i = 0; i < numNodes; i++) {
            path[i] = i;
        }
        shuffleArray(path);
        return path;
    }

    private void shuffleArray(int[] array) {
        Random rand = new Random();
        for (int i = array.length - 1; i > 0; i--) {
            int index = rand.nextInt(i + 1);
            int temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
    }

    private List<Integer> evaluateFitness(List<int[]> population) {
        List<Integer> fitness = new ArrayList<>();
        for (int[] path : population) {
            fitness.add(calculatePathLength(path));
        }
        return fitness;
    }

    private int calculatePathLength(int[] path) {
        int length = 0;
        for (int i = 0; i < path.length - 1; i++) {
            int from = path[i];
            int to = path[i + 1];
            if (graph[from][to] == Integer.MAX_VALUE) {
                return Integer.MAX_VALUE; // 不可达路径
            }
            length += graph[from][to];
        }
        // 回到起点
        int lastToFirst = graph[path[path.length - 1]][path[0]];
        if (lastToFirst == Integer.MAX_VALUE) {
            return Integer.MAX_VALUE; // 不可达路径
        }
        length += lastToFirst;
        return length;
    }

    private List<int[]> selection(List<int[]> population, List<Integer> fitness) {
        List<int[]> selected = new ArrayList<>();
        Random rand = new Random();

        // 计算总适应度
        int totalFitness = fitness.stream().mapToInt(f -> (f == Integer.MAX_VALUE ? 0 : f)).sum();

        if (totalFitness <= 0) {
            System.out.println("适应度为零，随机选择个体进行繁殖！");
            // 如果所有个体都无法访问（适应度为零），则随机选择个体
            for (int i = 0; i < population.size(); i++) {
                selected.add(population.get(rand.nextInt(population.size())));
            }
            return selected;
        }

        // 轮盘赌选择
        for (int i = 0; i < population.size(); i++) {
            int randomValue = rand.nextInt(totalFitness);
            int cumulativeFitness = 0;
            for (int j = 0; j < population.size(); j++) {
                cumulativeFitness += (fitness.get(j) == Integer.MAX_VALUE ? 0 : fitness.get(j));
                if (cumulativeFitness >= randomValue) {
                    selected.add(population.get(j));
                    break;
                }
            }
        }
        return selected;
    }

    private List<int[]> crossover(List<int[]> population) {
        List<int[]> offspring = new ArrayList<>();
        Random rand = new Random();

        // 进行交叉操作，生成新一代个体
        for (int i = 0; i < population.size(); i += 2) {
            int[] parent1 = population.get(i);
            int[] parent2 = population.get((i + 1) % population.size());

            int crossoverPoint = rand.nextInt(parent1.length);
            int[] child1 = new int[parent1.length];
            int[] child2 = new int[parent2.length];

            // 部分匹配交叉 (PMX)
            System.arraycopy(parent1, 0, child1, 0, crossoverPoint);
            System.arraycopy(parent2, 0, child2, 0, crossoverPoint);

            completePath(child1, parent2, crossoverPoint);
            completePath(child2, parent1, crossoverPoint);

            offspring.add(child1);
            offspring.add(child2);
        }
        return offspring;
    }

    private void completePath(int[] child, int[] parent, int crossoverPoint) {
        Set<Integer> visited = new HashSet<>();
        for (int i = 0; i < crossoverPoint; i++) {
            visited.add(child[i]);
        }

        int index = crossoverPoint;
        for (int i = 0; i < parent.length; i++) {
            if (!visited.contains(parent[i])) {
                child[index++] = parent[i];
            }
        }
    }

    private void mutate(List<int[]> population) {
        Random rand = new Random();
        for (int[] path : population) {
            if (rand.nextDouble() < MUTATION_RATE) {
                // 随机交换两个节点
                int index1 = rand.nextInt(path.length);
                int index2 = rand.nextInt(path.length);
                int temp = path[index1];
                path[index1] = path[index2];
                path[index2] = temp;
                System.out.println("发生变异！");
            }
        }
    }
}
